\documentclass{article}

\author{Tom Shortell, Mike DeLaurentis, James Rodgers}

\begin{document}
\title{CS 543 Fall 2011 Assignment 3}
\maketitle
\section{Implementation details}

\subsection{Handling TLB Misses}

We handle a TLB miss exception in the following way. In
VMProcess.handleException, we read the bad virtual address from the
register, ensure the page is loaded into physical memory, randomly
pick a slot in the tlb to evict, and then write the TranslationEntry
representing the page to the TLB. We acquire a lock before and after
this procedure, to ensure that two processes don't write to the TLB at
the same time.

In order to ``save the state'' of a process before a context switch,
we simply invalidate all the TLB entries.

\subsection{Inverted Page Table}

We use a single inverted page table to represent the mapping of
physical pages to their virtual addresses. The page table is
implemented in the {\tt nachos.vm.InvertedPageTable} class. It has a
{\tt table} property that as simply an array where the $i^{th}$ entry
corresponds to the $i^{th}$ page of physical memory. Each entry in the
table has a pid and a TranslationEntry. This allows us to use one
table to represent all the pages of physical memory, and associate
each page with a process.

The class also has an {\tt index} property, which is a HashMap that
maps $(pid, vpn)$ pairs to the integer index of the appropriate entry
in the {\tt table}.

The InvertedPageTable class has a {\tt write} method that takes a
process id and a TranslationEntry. It associates the page represented
by the TranslationEntry with the given pid, and overwrites the
appropriate record in the table.

InvertedPageTable has a {\tt getEntry} method that takes a pid and a
virtual page number, and returns the TranslationEntry for that (pid,
vpn) combination. It takes an additional boolean parameter that tells
it whether to throw an exception or return null if there is no entry
with the specified (pid, vpn) combination.

The class also has a {\tt nextVictim} method that chooses the next
page to evict from physical memory, using the clock algorithm. The
class has a {\tt hand} property that always points to the next entry
in the table that may be evicted. When nextVictim is called, we
advance the hand through the table and evict the first page we find
where the {\tt used} flag is false, setting the flag to false each
time we move past an entry.

It has a {\tt findFreePage} method that returns a physical page number
of a page that is not in use. This is used as a first attempt to try
to allocate memory for a program, before we have to resort to evicting
an existing page.

We did some testing on the performance of our page replacement
policy. We made a modified version of the matmult program, called
matmult2, that operates on 40x40 matrices rather than 20x20 in order
exercise the virtual memory a little more. We then wrote a script that
ran ``cat'', followed by ``matmult'' and ``matmult2'' five times
each. We ran this script in nachos ten times using a random page
replacement policy, and it resulted in an average of 408.3 page faults
per run. We then ran the same script in nachos using the clock page
replacement strategy, and it produced 335 page faults every time. So
for this benchmark, the clock strategy appears to be about $18\%$
better.

\subsection{Swap space}

The {\tt Swap} class is used to track pages that are in swap. It is an
inverted page table, fairly similar to the InvertedPageTable used to
track pages in physical memory. The swap is implemented as a simple
data file, and pages of memory are stored contiguously in the
file. The Swap class maintains some data structures to keep track of
the process and virtual page number for each record stored in the swap
file.

It has a {\tt table} property, where the $i^{th}$ entry corresponds to
the $i^{th}$ page stored in the swap file, and an {\tt index} property
which is an index into the table, keyed on $(pid, vpn)$ pairs. The
table is stored as an ArrayList and is allowed to grow as needed to
accomodate more pages.

It has a {\tt write} method, which writes a page from physical memory
into the swap file and updates its table and index accordingly. It
also has a {\tt read} method that reads a specified page from the swap
file back into physical memory.

\subsection{Lazy Loading}

The lazy loading is implemented on top of the Inverted Page Table and the swap space. 
The \textit{loadSections} function was modified to stop the loading of the pages into memory or swap and makes a list of them for the process to have when it needs them.
When the process realizes it needs them (in function \textit{swapIn}), it determines the page type and goes to locate it (either from executable or as an empty page). 
The executable pages do not go back to the executable once they have been read in and once read in they will use the swap as a protection method.
Stack/argument pages are created when requested. 
Security for stack pages is implemented via the \textit{swapIn} by putting a blankpage of zeroes into the memory location that is going to store the stack page when it is detected that it needs to be created. 

The explicit testing of the lazy loading was done using the debug log statements added to critical areas of the loading of pages. 
The individual provided coff files where used to conduct the tests (using cat.coff, matmult.coff, etc.).
The program's proper output was verified and the debug log statements where reviewed to compare that pages where being loaded. 
This was not overly complex because as soon as the \textit{loadSections} was modified to not load the pages nor touch the TLB, it became immediately evident where problems existed and could be remedied. 
The problems were evident because the coff program was not working properly. 

\section{Running}

The modified files in the \textit{vm} package are:
\begin{itemize}
\item InvertedPageTable.java
\item Swap.java
\item TranslationUtils.java
\item VMKernel.java
\item VMProcess.java
\end{itemize}

\noindent
The modified files in the \textit{userprog} package are:
\begin{itemize}
\item UserKernel.java
\item UserProcess.java
\end{itemize}

\noindent
The modified files in the \textit{threads} package are:
\begin{itemize}
\item Alarm.java
\item BasePriorityScheduler.java
\item ThreadedKernel.java
\end{itemize}

The program compiles and runs nearly exactly to proj2. 
Compiling entails using \textit{gmake} [enter]. 
Running the program is simple with \textit{nachos} (provided the script is in the proper path, otherwise \textit{../bin/nachos} works as well). 
The self tests have currently been disabled and nachos will run the sh.coff program to display the shell. 
As before this can be changed by using the \textit{-x} argument. 

\end{document}
